// ALERT: 此代码中的队列
//  1. 使用的是带头结点的循环队列（牺牲一个存储空间）；
//  2. 队头指针和队尾指针初值均认为是0

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode {
	ElemType data;
	struct LNode *next;
} LNode;

typedef struct {
	// 队头指针 队尾指针
	LNode *front, *rear;
} LQueue;


// FUNCTION: 初始化队列
void InitQueue(LQueue &Q) {
	// NOTE: 创建头结点，并用队头、队尾指针指向它
	Q.front = Q.rear = (LNode *) malloc(sizeof(LNode));


	// NOTE: 头结点的next指针为NULL
	Q.front->next = NULL;
}


// FUNCTION: 判队列空
bool isEmpty(LQueue Q) {
	if (Q.front == Q.rear) {
		return true;
	} else {
		return false;
	}
}


// FUNCTION: 入队——尾部插入法
// @param: val代表出队元素的值
bool EnQueue(LQueue &Q, ElemType val) {
	// NOTE: 执行入队操作
	// STEP: 新结点s初始化
	LNode *s = (LNode *) malloc(sizeof(LNode));

	// STEP: 判断结点是否申请失败
	if(!s) {
		return false;
	} else {
		s->data = val;
		s->next = NULL;
	}

	// STEP: 将新结点s插入队列中——让队尾元素的后继指向s
	Q.rear->next = s;

	// STEP: 更新队尾指针rear——始终指向队列尾部
	Q.rear = s;

	return true;
}


// FUNCTION: 出队——头部删除法
// @param: val代表出队元素的值
bool DeQueue(LQueue &Q, ElemType &val) {
	// NOTE: 出队合法性检查
	if (isEmpty(Q)) {
		return false;
	}


	// NOTE: 执行出队操作
	// STEP: 让指针p指向待出队结点
	// HINT: 需要出队的结点一定是头结点的下一个结点
	LNode *p = Q.front->next;

	// STEP: 保存结点值
	val = p->data;

	// STEP: 断链——将p所指结点从队列中断开
	Q.front->next = p->next;


	// NOTE: 删除结点p
	// HINT: 这里需要额外判断结点p是否为原队尾结点。因为，在一般情况下，p与队尾指针Q.rear的指向是不同的。但，此时Q.rear与p同指向。一旦p被free后，返回主函数。p作为临时变量被系统回收了。但是，Q.rear的指向关系依旧没变！Q.rear就成了野指针了！
	if (Q.rear == p) {
		// 队列置为空
		Q.rear = Q.front;
	}

	free(p);

	return true;
}


int main() {
	setbuf(stdout, NULL);

	// NOTE: Variable declaration
	// STEP: 定义栈结构体类型
	LQueue Q;

	// STEP: 定义变量，ElemType类型，用于存放弹队元素值
	ElemType value;

	// NOTE: 初始化队
	printf("Queue initiating...\n");
	InitQueue(Q);
	printf("Initiation finished.\n");

	printf("Whether queue is empty, or not?\n");
	if (isEmpty(Q)) {
		printf("Queue is empty.\n");
	} else {
		printf("Queue is not empty yet!\n");
	}

	// NOTE: 数据入队
	if (EnQueue(Q, 3)) {
		printf("EnQueue success!\n");
	} else {
		printf("EnQueue failed!\n");
	}

	if (EnQueue(Q, 4)) {
		printf("EnQueue success!\n");
	} else {
		printf("EnQueue failed!\n");
	}

	if (EnQueue(Q, 5)) {
		printf("EnQueue success!\n");
	} else {
		printf("EnQueue failed!\n");
	}

	if (EnQueue(Q, 6)) {
		printf("EnQueue success!\n");
	} else {
		printf("EnQueue failed!\n");
	}

	if (EnQueue(Q, 7)) {
		printf("EnQueue success!\n");
	} else {
		printf("EnQueue failed!\n");
	}


	// NOTE: 数据出队
	printf("DeQueue the top element of queue...\n");
	if (DeQueue(Q, value)) {
		printf("DeQueue success. Its value is %d\n", value);
	} else {
		printf("出队失败\n");
	}

	if (DeQueue(Q, value)) {
		printf("DeQueue success. Its value is %d\n", value);
	} else {
		printf("出队失败\n");
	}


	// NOTE: 其他操作
	if (EnQueue(Q, 8)) {
		printf("入队成功\n");
	} else {
		printf("入队失败\n");
	}

	return 0;
}
